package CodingTest;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = new int[]{12, 5, 9, 36, 8, 21, 7};
        System.out.println("初始状态：");
        showArray(array);

        initHeap(array);//这个应该也是堆排序的一部分，此处只是显示一下结果
        System.out.println("建堆之后：");
        showArray(array);

        heapSort(array);
        System.out.println("排序之后：");
        showArray(array);

    }
    public static void heapSort(int[] array){
        initHeap(array);
        int count = array.length;
        while(count > 1){
            int tmp = array[count -1];
            array[count - 1] = array[0];
            array[0] = tmp;
            count -- ;
            adjustHeap(array,count,0);
        }
    }
    public static void initHeap(int[] array){
        for(int root = array.length/2 - 1;root >= 0;root --){
            adjustHeap(array,array.length,root);
        }
            }
    public static void adjustHeap(int[] array,int count,int root){
        int maxChildIndex;
        while(root <= count/2 - 1){
            if(root == count/2 - 1 && count%2 == 0) {
                maxChildIndex = 2 * root + 1;
            }
            else{
                int leftChildIndex = 2*root + 1;
                int rightChildIndex = 2*root + 2;
                maxChildIndex = array[leftChildIndex] > array[rightChildIndex]?leftChildIndex:rightChildIndex;
            }
            if(array[root] < array[maxChildIndex]){
                int tmp = array[root];
                array[root] = array[maxChildIndex];
                array[maxChildIndex] = tmp;
                root = maxChildIndex;
            }else{
                return;
            }
        }
    }

    public static void showArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ((i == array.length - 1) ? "\n" : " "));
        }
    }

}